package com.clps.algorithm.chapter13.分割回文子字符串;

import java.util.LinkedList;
import java.util.List;

/**
 * 输入一个字符串,要求将它分割成若干子字符串使得每个子字符串都是回文。
 * 请列出所有可能的分割方法。例如，输入"google"，将输出3中符合条件的分割方法，
 * 分别是["g", "o", "o", "g", "l", "e"]、["g", "oo", "g", "l", "e"]和["goog", "l", "e"]。
 */
public class demo01 {

    public static void main(String[] args) {

    }

    public List<List<String>> partition(String s){
        List<List<String>> result = new LinkedList<>();
        helper(s,0,new LinkedList<>(),result);
        return  result;
    }

    private void helper(String str, int start, LinkedList<String> substrings, List<List<String>> result) {
        if(start == str.length()){
            result.add(new LinkedList<>(substrings));
            return;
        }


        for (int i = start; i < str.length(); i++) {
            if(isPalomdrome(str,start,i)){
                substrings.add(str.substring(start,i+1));
                helper(str,i+1,substrings,result);
                substrings.removeLast();
            }
        }
    }

    private boolean isPalomdrome(String str, int start, int end) {
        while (start<end){
            if(str.charAt(start++)!=str.charAt(end--)){
                return  false;
            }
        }
        return true;
    }
}
